package com.chj.jz.dp.class06;

// https://www.jiuzhang.com/problem/regular-expression-matching/#tag-lang-java
public class Code06_RegularExpressionMatching {
	/**
	 * @param s:
	 *            A string
	 * @param p:
	 *            A string includes "." and "*"
	 * @return: A boolean
	 */
	public static boolean isMatch(String s, String p) {
		char[] A = s.toCharArray();
		char[] B = p.toCharArray();
		int m = A.length;
		int n = B.length;

		boolean[][] f = new boolean[m + 1][n + 1];
		int i, j;
		for (i = 0; i <= m; i++) {
			for (j = 0; j <= n; j++) {
				if (i == 0 && j == 0) {
					f[i][j] = true;
					continue;
				}

				if (j == 0) {
					f[i][j] = false;
					continue;
				}

				// j > 0
				f[i][j] = false;
				if (B[j - 1] != '*') {
					if (i > 0 && (B[j - 1] == '.' || B[j - 1] == A[i - 1])) {
						f[i][j] = f[i - 1][j - 1];
					}
					
				} else {
					// c* represents 0 c
					if (j > 1) {
						f[i][j] |= f[i][j - 2];
					}

					// c* represents >=1 c (c=B[j-2])
					if (i > 0 && j > 1) {
						if (B[j - 2] == '.' || B[j - 2] == A[i - 1]) {
							f[i][j] |= f[i - 1][j];
						}
					}
				}
			}
		}

		return f[m][n];
	}
	
	public static void main(String[] args) {
		// 输入: "ABCD" and "EDCA"
		{
			String str1 = "aa";
			String str2 = "a";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aa";
			String str2 = "a*";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aab";
			String str2 = "c*a*b*";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "ab";
			String str2 = ".*";
			System.out.println(isMatch(str1, str2));
		}
	}
}
